Foreword

Creative Scala is aimed at developers who have no prior experience in Scala. It is designed to give you a fun introduction to functional programming. We assume you have some familiarity with another programming language but little or no experience with Scala or other functional languages.

Our goal is to demonstrate the building blocks that Scala developers use to create programs in a clear, succinct, declarative manner. Working through the exercises in the book should take a few hours, after which we hope you will have a feel of what Scala can do for your applications.

Although this book will give you the basic mental model required to become competent with Scala, you won’t finish knowing everything you need to be self-sufficient. For further advancement we recommend considering one of the many excellent Scala textbooks out there, including our own Essential Scala.

If you are working through the exercises on your own, we highly recommend joining our Gitter chat room to provide get help with the exercises and provide feedback on the book.

The text of Creative Scala is open souce, as is the source code for the Doodle drawing library used in the exercises. You can grab the code from our Github account. Contact us on Gitter or by email if you would like to contribute.

Thanks for downloading and happy creative programming!

—Dave and Noel

Notes on the Early Access Edition

Acknowledgements

Creative Scala was written by Dave Gurnell and Noel Welsh. Many thanks to Richard Dallaway, Jonathan Ferguson, and the team at Underscore for their invaluable contributions and extensive proof reading.

Thanks also to the many people who pointed out errors or made suggestions to improve the book: Neil Moore, and many more for whom we didn’t record the name.

1 Getting Started

Installing required software - Text editor and SBT OR IntelliJ and SBT plugin - Doodle skeleton

Run a simple program to check everything works.

2 Expressions, Values, and Types

Scala programs have three fundamental building blocks: expressions, values, and types. In this section we explore these concepts.

Here’s a very simple expression:

1 + 2

An expression is a fragment of Scala code. We can write expressions in an a text editor, or on a piece of paper, or on a wall. You get the idea.

Expressions are like writing. Just like writing must be read for it to have any effect on the world (and the reader has to understand the language the writing is written in), the computer must run an expression for it to have an effect. The result of running an expression is a value. Value’s live in the computer’s memory, in the same way that the result of reading some writing lives in the reader’s head. We will also say expressions are evaluated or executed to describe the process of transforming them into values.

We can evaluate expressions immediately by writing them at the console and pressing “Enter” (or “Return”). Try it now.

1 + 2

The console responds with the value the expression evaluates to, and the type of the expression.

The expression 1 + 2 evaluates to the value 3. We can write down the number three here on the page, but the real value is something stored in the computer’s memory. In this case, it is a 32-bit integer represented in two’s-complement. The meaning of “32-bit integer represented in two’s-complement” is not important. I just mention it to emphasise the fact the computer’s representation of the value 3 is the true value, not the numeral written here or by the console.

Types are the final piece of the puzzle. A type is anything we can determine about a program without running it. The expression 1 + 2 has the type Int, which means we should interpret the value the expression evaluates to as an integer. This further means we can write further expressions that make sense for integers with the expression result of this expression. We could add, subtract, multiply, or divide, but we couldn’t convert it to lowercase, for example.

Types will often tell us how we should understand the value (the “stuff” in the computer’s memory) that an expression evaluates to. Should we understand it as an integer or as a stream of points giving the current position of the mouse? The types will tell us. We can use types for other things, including things that don’t have any representation at run-time. These uses are a bit more advanced than we’ll get into here, but don’t make the mistake of thinking that types correspond to value. Types only exist at compile-time in Scala. There is not necessarily any representation at runtime of the type of the expression that produced a given a value.

Before a Scala program is run, it must be compiled. Compilation checks that a program makes sense. It must be syntactically correct, meaning it must be written according to the rules of Scala. For example (1 + 2) is syntactically correct, but (1 + 2 is not. It must also type check, meaning the types must be correct for the operations we’re trying to do. 1 + 2 type checks (we are adding integers), but 1.toUpperCase does not (there is no concept of upper and lower case for numbers.)

Only programs that successfully compile can be run. We can think of compilation as being analogous to the rules of grammar in writing. The sentence “F$Rf fjrmn;l df.fd” is syntactically incorrect in English. The arrangement of letters doesn’t form any words. The sentence “dog fly a here no” is made out of valid words but their arrangement breaks the rules of grammar—analogous to the type checks that Scala performs.

We will talk about compile-time as the time when a code is compiled, and run-time as the time when the code is run.

2.1 Literal Expressions

We’ll now start to explore the various forms of expressions in Scala, starting with the simplest expressions literals. Here’s a literal expression:

3

A literal evaluates to “itself.” How we write the expression and how the console prints the value are the same. Remember though, there is a difference between the written representation of a value and its actual representation in the computer’s memory.

Scala has many different forms of literals. We’ve already seen Int literals. There is a different type, and a different literal syntax, for what are called floating point numbers. This corresponds to a computer’s approximation of the real numbers. Here’s an example:

0.1

As you can see, the type is called Double.

Numbers are well and good, but what about text. Scala’s String type represents a sequence of characters. We write literal strings by putting their contents in double quotes.

"To be fond of dancing was a certain step towards falling in love."

Sometimes we want to write strings that span several lines. We can do this by using triple double quotes, as below.

"""
A new, a vast, and a powerful language is developed for the future use of analysis,
in which to wield its truths so that these may become of more speedy and accurate
practical application for the purposes of mankind than the means hitherto in our
possession have rendered possible. 

  -- Ada Lovelace, the world's first programmer
"""

A String is a sequence of characters. Characters themselves have a type, Char, and character literals are written in single quotes.

'a'

Finally we’ll look at the literal representations of the Boolean type, named after English logician George Boolean. The fancy name just means a value that can be either true or false, and this indeed is how we write boolean literals.

true
false

With literal expressions we can create values, but we won’t get very far if we can’t somehow interact with the values we’ve created. We’ve seen a few examples of more complex expressions like 1 + 2. In the next section we’ll learn about objects and methods, which will allow to understand how this, and more interesting expressions, work.

2.2 Values are Objects

In Scala all values are objects. An object is a grouping of data and operations on that data. For example, 2 is an object. The data is the integer 2, and the operations on that data are familiar operations like +, -, and so on. We call operations of an object the object’s methods.

2.2.1 Method Calls

We interact with objects by calling or invoking methods. For example, we can get the uppercase version of a String by calling its toUpperCase method.

"Titan!".toUpperCase

Some methods accept parameters or arguments, which control how the method works. The take method, for example, takes characters from a String. We must pass a parameter to take to specify how many characters we want.

"Gilgamesh went abroad in the world".take(3)
"Gilgamesh went abroad in the world".take(9)

A method call is an expression, and thus evaluates to an object. This means we can chain method calls together to make more complex programs:

"Titan!".toUpperCase.toLowerCase

anExpression.methodName(param1, ...)

anExpression.methodName

2.2.2 Operators

We have said that all values are objects, and we call methods with the syntax object.methodName(parameter). How then do we explain expressions like 1 + 2?

In Scala, and expression written a.b(c) can be written a b c. So these are equivalent:

1 + 2
1.+(2)

This second way of calling a method is known an operator style.

2.3 Types

Now we can write more complex expressions we can talk a little more about types.

One use of types is stopping us from calling methods that don’t exist. The type of an expression tells the compiler what methods exist on the value it evaluates to. Our code won’t compile if we try to call to a method that doesn’t exist. Here are some simple examples.

"Brontë" / "Austen"
1.take(2)

It really is the type of the expression that determines what methods we can call, which we can demonstrate by calling methods on the result of more complex expressions.

(1 + 3).take(1)

This process of type checking also applies to the parameter of methods.

1.min("zero")

Types are a property of expressions and thus exist at compile-time (as we have discussed before.) This means we can determine the type of expression even if evaluating it results in an error at run-time. For example, dividing an Int by zero causes a run-time error.

1 / 0

The expression 1 / 0 still has a type, and we can get that type from the console as shown below.

:type 1 / 0
// Int

We can also write a compound expression including a sub-expression that will fail at run-time.

(2 + (1 / 0) + 3)

This expression also has a type.

:type (2 + (1 / 0) + 3)
// Int

2.4 Exercises

2.4.0.1 Arithmetic

Write an expression using integer literals, addition, and subtraction that evaluates to 42.

1 + 43 - 2

2.4.0.2 Appending Strings

Join together two strings (known as appending strings) using the ++ method. Write equivalent expressions using both the normal method call style and operator style.

"It is a truth ".++("universally acknowledged")
"It is a truth " ++ "universally acknowledged"

2.4.0.3 Precedence

In mathematics we learned that some operators take precedence over others. For example, in the expression 1 + 2 * 3 we should do the multiplication before the addition. Do the same rules hold in Scala?

1 + 2 * 3
1 + (2 * 3)
(1 + 2) * 3

2.4.0.4 Types and Values

Which of the following expressions will not compile? Of the expressions that will compile, what is their type? Which expressions fail at run-time?

1 + 2

"3".toInt

"Electric blue".toInt

"Electric blue".take(1)

"Electric blue".take("blue")

1 + ("Moonage daydream".indexOf("N"))

1 / 1 + ("Moonage daydream".indexOf("N"))

1 / (1 + ("Moonage daydream".indexOf("N")))

1 + 2

"3".toInt

"Electric blue".toInt

"Electric blue".take(1)

"Electric blue".take("blue")

1 + ("Moonage daydream".indexOf("N"))

1 / 1 + ("Moonage daydream".indexOf("N"))

1 / (1 + ("Moonage daydream".indexOf("N")))

2.4.0.5 Floating Point Failings

When we introduced Doubles, I said they are an approximation to the real numbers. Why do you think this is? Think about representing numbers like ⅓ and π. How much space would it take to represent these numbers in decimal?

2.4.0.6 Beyond Expressions

In our current model of computation there are only three components: expressions (program text) with types, that evaluate to values (something within the computer’s memory). Is this sufficient? Could we write a stock market or a computer game with just this model? Can you think of ways to extend this model?

3 Computing With Pictures

So far we have computed using numbers, strings, and other simple objects. This is not particularly interesting. From here on out we will focus our attention to computing with pictures, and later to animations. Pictures offer us more immediate creative opportunities, and they make our program output tangible in a way that other methods can’t deliver.

We’ll use a library called Doodle to help us with creating graphics. In this chapter we will learn the basics of Doodle.

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

3.1 Images

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

Let’s start with some simple shapes, programming at the console as we’ve done before.

Image.circle(10)

What is happening here? Image is an object and circle a method on that object. We pass to circle a parameter, 10 that gives the radius of the circle we’re constructing. Note the type of the result—an Image.

We can also write just circle(10), as if you run the console within Doodle it automatically makes this and other methods to construct images available.

circle(10)

We draw the circle by calling the draw method.

circle(10).draw

A window should appear as shown in fig. 1.

Figure 1: A circle

Doodle supports a handful of “primitive” images: circles, rectangles, and triangles. Let’s try drawing a rectangle.

rectangle(50, 100).draw

The output is shown in fig. 2.

Figure 2: A rectangle

Finally let’s try a triangle, for which the output is shown in fig. ??.

triangle(60, 40).draw

A triangle

Exercises

I Go Round in Circles

Create circles that are 1, 10, and 100 units wide. Now draw them!

circle(1)
circle(10)
circle(100)

circle(1).draw
circle(10).draw
circle(100).draw

My Type of Art

What is the type of a circle? A rectangle? A triangle?

:type circle(10)
// doodle.core.Image
:type rectangle(10, 10)
// doodle.core.Image
:type triangle(10, 10)
// doodle.core.Image

Not My Type of Art

What’s the type of drawing an image? What does this mean?

:type circle(10).draw
// Unit

()

:type ()
// Unit

3.2 Layout

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

We can seen how to create primitive images. We can combine together images using layouts methods to create more complex images. Try the following code—you should see a circle and a rectangle displayed beside one another, as in fig. 3.

(circle(10) beside rectangle(10, 20)).draw

Figure 3: A circle beside a rectangle

Doodle contains several layout methods for combining images, described in tbl. 1. Try them out now to see what they do.

Exercises

The Width of a Circle

Create the picture fig. 4 using the layout methods and basic images we’ve covered so far.

Figure 4: The width of a circle

(circle(20) beside circle(20) beside circle(20)) on circle(60)

3.3 Color

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

In addition to layout, Doodle has some simple operators to add a splash of colour to our images. Try these out the methods described in tbl. 2 to see how they work.

Doodle has various ways of creating colours. The simplest are the predefined colours in CommonColors.scala. Some of the most commonly used are described in tbl. 3.

3.3.0.1 Exercise

3.3.0.1.1 Evil Eye

Make the image in fig. 5, designed to look like a traditional amulet protecting against the evil eye. I used cornflowBlue for the iris, and darkBlue for the outer color, but experiment with your own choices!

Figure 5: No evil eyes here!

((circle(10) fillColor Color.black) on
 (circle(20) fillColor Color.cornflowerBlue) on
 (circle(30) fillColor Color.white) on
 (circle(50) fillColor Color.darkBlue))

3.4 Creating Colors

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

We’ve seen how to use predefined colors in our images. What about creating our own colors? In this section we will see how to create colors of our own, and transform existing colors into new ones.

3.4.1 RGB Colors

Computers work with colors defined by mixing together different amounts of red, green, and blue. This “RGB” model is an additive model of color. Each red, green, or blue component can have a value between zero and 255. If all three components are set to the maximum of 255 we get pure white. If all components are zero we get black.

We can create our own RGB colors using the rgb method on the Color object. This method takes three parameters: the red, green, and blue components. These are numbers between 0 and 255, called an UnsignedByte¹. There is no literal expression for UnsignedByte like there is for Int, so we must convert an Int to UnsignedByte. We can do this with the uByte method. An Int can take on more values that an UnsignedByte, so if the number is too small or too large to be represented as a UnsignedByte it will be converted to the closest values is the range 0 to 255. These examples illustrate the conversion.

0.uByte
255.uByte
128.uByte
-100.uByte // Too small, is transformed to 0
1000.uByte // Too big, is transformed to 255

(Note that UnsignedByte is a feature of Doodle. It is not something provided by Scala.)

Now we know how to construct UnsignedBytes we can make RGB colors.

Color.rgb(255.uByte, 255.uByte, 255.uByte) // White
Color.rgb(0.uByte, 0.uByte, 0.uByte) // Black
Color.rgb(255.uByte, 0.uByte, 0.uByte) // Red

3.4.2 HSL Colors

The RGB color representation is not very easy to use. The hue-saturation-lightness (HSL) format more closely correponds to how we perceive color. In this representation a color consists of:

• hue, which is an angle between 0 and 360 degrees giving a rotation around the color wheel.
• saturation, which is a number between 0 and 1 giving the intensity of the color from a drab gray to a pure color; and
• lightness between 0 and 1 giving the color a brightness varying from black to pure white.

A color wheel showing changes in hue (rotations) and lightness (distance from the center) with saturation fixed at 1.

A gradient showing how changing saturation effects color, with hue and lightness held constant. Saturation is zero on the left and one on the right.

We can construct a color in the HSL representation using the Color.hsl method. This method takes as parameters the hue, saturation, and lightness. The hue is an Angle. We can convert a Double to an Angle using the degrees (or radians) methods.

0.degrees
180.degrees
3.14.radians

Saturation and lightness are both normalized to between 0.0 and 1.0. We can convert a Double to a normalized value with the .normalized method.

0.0.normalized 
1.0.normalized
1.2.normalized // Too big, is clipped to 1.0
-1.0.normalized // Too small, is clipped to 0.0

We can now create colors using the HSL representation.

Color.hsl(0.degrees, 0.8.normalized, 0.6.normalized) // A pastel red

To view this color we can render it in a picture. See fig. 6 for an example.

Figure 6: Rendering pastel red in a triangle

3.4.3 Manipulating Colors

The effectiveness of a composition often depends as much on the relationships between colors as the actual colors used. Colors have several methods that allow us to create a new color from an existing one. The most commonly used ones are:

• spin, which rotates the hue by an Angle;
• saturate and desaturate, which respectively add and subtract a Normalised value from the color; and
• lighten and darken, which respecitvely add and subtract a Normalised value from the lightness.

For example,

((circle(100) fillColor Color.red) beside 
  (circle(100) fillColor Color.red.spin(15.degrees)) beside
    (circle(100) fillColor Color.red.spin(30.degrees))).lineWidth(5.0)

produces fig. 7.

Figure 7: Three circles, starting with Color.red and spinning by 15 degrees for each successive circle

Here’s a similar example, this time manipulating saturation and lightness, shown in fig. 8.

(((circle(20) fillColor (Color.red darken 0.2.normalized))
  beside (circle(20) fillColor Color.red)
  beside (circle(20) fillColor (Color.red lighten 0.2.normalized))) above
((rectangle(40,40) fillColor (Color.red desaturate 0.6.normalized)) 
  beside (rectangle(40,40) fillColor (Color.red desaturate 0.3.normalized))
  beside (rectangle(40,40) fillColor Color.red)))

Figure 8: The top three circles show the effect of changing lightness, and the bottom three squares show the effect of changing saturation.

3.4.4 Transparency

We can also add a degree of transparency to our colors, by adding an alpha value. An alpha value of 0.0 indicates a completely transparent color, while a color with an alpha of 1.0 is completely opaque. The methods Color.rgba and Color.hsla have a fourth parameter that is a Normalized alpha value. We can also create a new color with a different transparency by using the alpha method on a color. Here’s an example, shown in fig. 9.

((circle(40) fillColor (Color.red.alpha(0.5.normalized))) beside
 (circle(40) fillColor (Color.blue.alpha(0.5.normalized))) on
 (circle(40) fillColor (Color.green.alpha(0.5.normalized))))

Figure 9: Circles with alpha of 0.5 showing transparency

Exercises

Complementary Triangles

Create three triangles, arranged in a triangle, with complementary colors. Complementary colors are colors that are similar in hue. See a (fairly elaborate) example in fig. 10.

Figure 10: Complementary triangles. The colors chosen are variations on darkSlateBlue

((triangle(40, 40)
       lineWidth 6.0
       lineColor Color.darkSlateBlue
       fillColor (Color.darkSlateBlue lighten 0.3.normalized saturate 0.2.normalized spin 10.degrees)) above
  ((triangle(40, 40)
      lineWidth 6.0
      lineColor (Color.darkSlateBlue spin (-30.degrees))
      fillColor (Color.darkSlateBlue lighten 0.3.normalized saturate 0.2.normalized spin (-20.degrees))) beside
     (triangle(40, 40)
        lineWidth 6.0
        lineColor (Color.darkSlateBlue spin (30.degrees))
        fillColor (Color.darkSlateBlue lighten 0.3.normalized saturate 0.2.normalized spin (40.degrees)))))

3.5 Exercises

Exercise: Compilation Target

Create a line drawing of an archery target with three concentric scoring bands:

Simple archery target

For bonus credit add a stand so we can place the target on a range:

Archery target with a stand

(Circle(10) on Circle(20) on Circle(30)).draw

(
  Circle(10) on
  Circle(20) on
  Circle(30) above
  Rectangle(6, 20) above
  Rectangle(20, 6)
).draw

Exercise: Stay on Target

Colour your target red and white, the stand in brown (if applicable), and some ground in green:

Colour archery target

(
  ( Circle(10) fillColor Color.red ) on
  ( Circle(20) fillColor Color.white ) on
  ( Circle(30) fillColor Color.red lineWidth 2 ) above
  ( Rectangle(6, 20) above Rectangle(20, 6) fillColor Color.brown ) above
  ( Rectangle(80, 25) lineWidth 0 fillColor Color.green )
).draw

4 Writing Larger Programs

We’re getting to the point where it’s inconvenient to type programs into the console. In this chapter we’ll learn about two tools for writing larger programs:

• saving programs to a file so we don’t have to type code over and over again;
• giving names to values so we can reuse them.

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

4.1 Working Within the Console

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

Your text editor or IDE will allow you to save code to a file, but we need to save them in the right place so the Scala compiler can find them. If you’re working from the Doodle template you should save your code in the directory src/main/scala/.

How do we use code that we saved to a file from the console? There is a special command, that only works from the console, that allows us to run code saved in a file. This command is called :paste². We follow :paste with the name of the file we want to run. For example, if we save in the file src/main/scala/Example.scala the expression

circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed

we can then run this code by writing at the console

:paste src/main/scala/Example.scala
// res0: doodle.core.Image = ContextTransform(<function1>,ContextTransform(<function1>,Circle(100.0)))

Note the value has been given the name res0 in the example above. If you’re following along, the name in your console might end with a different number depending on what you’ve already typed into the console. We can draw the image by evaluating res0.draw (or the correct name for your console).

4.1.1 Tips for Using the Console

Here are a few tips for using the console more productively:

• If you press the up arrow you’ll get the last thing you typed into the console. Handy to avoid having to type in those long file names over and over again! You can press up multiple times to go through the history of your interactions at the console.

• You can press the Tab key to get the console to suggest completions for code, but unfortunately not file names, you’re typing. For example, if you type Stri and then press Tab, the console will show possible completions. Type Strin and the console will complete String for you.

4.2 Coding Outside the Console

The code we’ve been writing inside the console will cause problems running outside the console. For example, put the following code into Example.scala in the src/main/scala.

circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed

Now restart SBT and try to enter the console. You should see an error similar to

[error] src/main/scala/Example.scala:1: expected class or object definition
[error] circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed
[error] ^
[error] one error found

You’ll see something similar if you’re using an IDE.

The problem is this:

• Scala is attempting to compile all our code before the console starts; and
• there are restrictions on code written in files that don’t apply to code written directly in the console.

We need to know about these restrictions and change how we write code in files accordingly.

The error message gives us some hint: expected class or object definition. We don’t yet know what a class is, but we do know about objects—all values are objects. In Scala all code in a file must be written inside an object or class. We can easily define an object by wrapping an expression like the below.

object Example {
  (circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed).draw
}

Now the code won’t compile for a different reason. I get a lot of errors similar to

[error] doodle/shared/src/main/scala/doodle/examples/Example.scala:2: not found: value circle
[error]   (circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed).draw
[error]    ^

The compiler is saying that we’ve used a name, circle, but the compiler doesn’t know what value this name refers to. It will have a similiar issue with Color in the code above. We’ll talk in more details about names in just a moment. Right now let’s tell the compiler where it can find the values for these names by adding some import statements. The name Color is found inside a package called doodle.core, and the name circle is within the object Image that is in doodle.core. We can tell the compiler to use all the name in doodle.core, and all the names in the the object Image by writing

import doodle.core._
import doodle.core.Image._

There are a few other names that the compiler will need to find for the complete code to work. We can import these with the lines

import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

We should place all these imports at the top of the file, so the complete code looks like

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

object Example {
  (circle(100) fillColor Color.paleGoldenrod lineColor Color.indianRed).draw
}

With this in place the code should compile without issue.

Now when we go to the console within SBT we can refer to our code using the name, Example, that we’ve given it.

Example // draws the image

Exercise

If you haven’t done so already, save the code above in the file src/main/scala/Example.scala and check that the code compiles and you can access it from the console.

Introduce names, val, and imports.

5 The Substitution Model of Evaluation

6 Methods

7 Structural Recursion

In this chapter we see our first major pattern for structuring computations: structural recursion over the natural numbers. That’s quite a mouthful, so let’s break it down:

• By a pattern, we mean a way of writing code that is useful in lots of different contexts. We’ll encounter structural recursion in many different situations throughout this book.

• By the natural numbers we mean the whole numbers 0, 1, 2, and upwards.

• By recursion we mean something that refers to itself. Structural recursion means a recursion that follows the structure of the data it is processing. If the data is recursive (refers to itself) then the structural recursion will also refer to itself. We’ll see in more detail what this means in a moment.

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

7.1 A Line of Boxes

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

Let’s start with an example, drawing a line or row of boxes as in fig. 11.

Figure 11: Six boxes filled with Royal Blue

Let’s define a box to begin with.

val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)

Then one box in a row is just

val oneBox = aBox

If we want to have two boxes side by side, that is easy enough.

val twoBoxes = aBox beside oneBox

Similarly for three.

val threeBoxes = aBox beside twoBoxes

And so on for as many boxes as we care to create.

You might think this is an unusual way to create these images. Why not just write

val threeBoxes = aBox beside aBox beside aBox

for example? These two definitions are equivalent. We’ve chosen to write later images in terms of earlier ones to emphasise the structure we’re dealing with, which is building up to structural recursion.

Writing images in this way could get very tedious. What we’d really like is some way to tell the computer the number of boxes we’d like. More technically, we would like to abstract over the expressions above. We learned in the previous chapter that methods abstract over expressions, so let’s try to write a method to solve this problem.

We’ll start by writing a method skeleton that defines, as usual, what goes into the method and what it evaluates to. In this case we supply an Int count, which is the number of boxes we want, and we get back an Image.

def boxes(count: Int): Image =
  ???

Now comes the new part, the strucural recursion. We noticed that threeBoxes above is defined in terms of twoBoxes, and twoBoxes is itself defined in terms of box. We could even define box in terms of no boxes, like so:

val oneBox = aBox beside Image.empty

Here we used Image.empty to represent no boxes.

Imagine we had already implemented the boxes method. We can say the following properties of boxes always hold, if it is correctly implemented:

• boxes(0) == Image.empty
• boxes(1) == aBox beside boxes(0)
• boxes(2) == aBox beside boxes(1)
• boxes(3) == aBox beside boxes(2)

The last three properties all have the same general shape. We can describe all of them, and any case for n > 0, with the single property boxes(n) == aBox beside boxes(n - 1). So we’re left with two properties

• boxes(0) == Image.empty
• boxes(n) == aBox beside boxes(n-1)

These two properties completely define the behavior of boxes. In fact we can implement boxes by converting these properties into code.

A full implementation of boxes is

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }

Try it and see what results you get! This implementation is only tiny bit more verbose than the properties we wrote above, and is our first structural recursion over the natural numbers.

At this point we have two questions to answer. Firstly, how does this match expression work? More importantly, is there some general principle we can use to create methods like this on our own? Let’s take each question in turn.

Exercise: Stacking Boxes

Even before we get into the details of match expressions you should be able to modify boxes to produce an image like fig. 12.

At this point we’re trying to get used to the syntax of match, so rather than copying and pasting boxes write it all out by hand again to get some practice.

Figure 12: Three stacked boxes filled with Royal Blue

def stackedBoxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox beside stackedBoxes(n-1)
  }

7.2 Match Expressions

In the previous section we saw the match expression

count match {
  case 0 => Image.empty
  case n => aBox beside boxes(n-1)
}

How are we to understand this new kind of expression, and write our own? Let’s break it down.

The very first to say is that match is indeed an expression, which means it evaluates to a value. If it didn’t, the boxes method would not work!

To understand what it evaluates to we need more detail. A match expression in general has the shape

<anExpression> match {
  case <pattern1> => <expression1>
  case <pattern2> => <expression2>
  case <pattern3> => <expression3>
  ...
}

<anExpression>, concretely count in the case above, is the expresssion that evaluates to the value we’re matching against. The patterns <pattern1> and so on are matched against this value. So far we’ve seen two kinds of patterns:

• a literal (as in case 0) which matches exactly the value that literal evaluates to; and
• a wildcard (as in case n) which matches anything, and introduces a binding within the right-hand side expression.

Finally, the right-hand side expressions, <expression1> and so on, are just expresssions like any other we’ve written so far. The entire match expression evalutes to the value of the right-hand side expression of the first pattern that matches. So when we call boxes(0) both patterns will match (because the wildcard matches anything), but because the literal pattern comes first the expression Image.empty is the one that is evaluated.

A match expression that checks for all possible cases is called an exhaustive match. If we can assume that count is always greater or equal to zero, the match in boxes is exhaustive.

Once we’re comfortable with match expressions we need to look at the structure of the natural numbers before we can explain structural recursion over them.

Exercises

Guess the Result

Let’s check our understanding of match by guessing what each of the following expressions evaluates to, and why.

"abcd" match {
  case "bcde" => 0
  case "cdef" => 1
  case "abcd" => 2
}

1 match {
  case 0 => "zero"
  case 1 => "one"
  case 1 => "two"
}

1 match {
  case n => n + 1
  case 1 => 1000
}

1 match {
  case a => a
  case b => b + 1
  case c => c * 2
}

No Match

What happens if no pattern matches in a match expression? Take a guess, than right a match expression that fails to match and see if you managed to guess correctly. (At this point we have no reason to expect any particular behavior so any reasonable guess will do.)

2 match {
  case 0 => "zero"
  case 1 => "one"
}

7.3 The Natural Numbers

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)

The natural numbers are the whole numbers, or integers, greater than or equal to zero. In other words the numbers 0, 1, 2, 3, … (Some people define the natural numbers as starting at 1, not 0. It doesn’t greatly matter for our purposes which definition you choose, but here we’ll assume they start at 0.)

One interesting property of the natural numbers is that we can define them recursively. That is, we can define them in terms of themselves. This kind of circular definition seems like it would lead to nonsense. We avoid this by including in the definition a base case that ends the recursion. Concretely, the definition is:

A natural number n is

• 0; or
• 1 + m, where m is a natural number.

The case for 0 is the base case, whilst the other case is recursive as it defines a natural number n in terms of a natural number m. Because m is always smaller than n, and the base case is the smallest possible natural number, this definition defines all of the natural numbers.

Given a natural number, say, 3, we can break it down using the definition above as follows:

3 = 1 + 2 = 1 + (1 + 1) = 1 + (1 + (1 + 0))

We use the recursive rule to expand the equation, until we cannot use it any more. We then use the base case to stop the recursion.

7.4 Structural Recursion

Now onto structural recursion. The structural recursion pattern for the natural numbers gives us two things:

• a reusable code skeleton for processing any natural number; and
• the guarantee that we can use this skeleton to implement any computation on natural numbers.

Remember we wrote boxes as

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }

When we developed boxes we just seemed to stumble upon this pattern. Here we see that this pattern follows directly from the definition of the natural numbers. Remember the recursive definition of the natural numbers: a natural number n is

• 0; or
• 1 + m, where m is a natural number.

The patterns in the match expression exactly match this definition. The expression

count match {
  case 0 => ???
  case n => ???
}

means we’re checking count for two cases, the case when count is 0, and the case when count is any other natural number n (which is 1 + m).

The right hand side of the match expression says what we do in each case. The case for zero is Image.empty. The case for n is aBox beside boxes(n-1).

Now for the really important point. Notice that the structure of the right-hand side mirrors the structure of the natural number we match. When we match the base case 0, our result is the base case Image.empty. When we match the recursive case n the structure of the right hand side matches the structure of the recursive case in the definition of natural numbers. The definition states that n is 1 + m. On the right-hand side we replace 1 with aBox, we replace + with beside, and we recursively call boxes with m (which is n-1) where the definition recurses.

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }

To reiterate, the left hand side of the match expression exactly matches the definition of natural numbers. The right-hand also matches the definition but we replace natural numbers with images. The image that is equivalent to zero is Image.empty. The image that is equivalent to 1 + m is aBox beside boxes(m).

This general pattern holds for anything we care to write that transforms the natural numbers into some other type. We always have a match expression. We always have the two patterns, corresponding to the base and recursive cases. The right hand side expressions always consist of the base case, and the recursive case which itself hasa result specific substitute for 1 and +, and a recursive call for n-1.

The general pattern is

def <doSomething>(count: Int): <Result> =
  count match {
    case 0 => <resultBase>
    case n => <resultUnit> <add> <doSomething>(n-1)
  }

where <Result>, <resultBase>, <resultUnit>, and <add> are specific to the problem we’re solving. So to implement a structural recursion over the natural numbers we must

• recognise the method we’re writing has a natural number as it’s input;
• work out the result type; and
• decide what should be the base, unit, and addition for the result.

We’re now ready to go explore the fun that can be had with this simple but powerful tool.

Exercises

Cross

Our first exercise is to create a method cross that will generate cross images. fig. 13 shows four cross images, which correspond to calling the method cross with 0 to 3.

The method skeleton is

def cross(count: Int): Image =
  ???

Figure 13: Crosses generated by count from 0 to 3.

What pattern will we use to fill in the body of cross? Write out the pattern.

def cross(count: Int): Image =
  count match {
    case 0 => <resultBase>
    case n => <resultUnit> <add> cross(n-1)
  }

Now we’ve identified the pattern we’re using, we need to fill in the problem specific parts:

• the base case; and
• the unit and addition operators.

Hint: use fig. 13 to identify the elements above.

Now finish the implementation of cross.

def cross(count: Int): Image = {
  val unit = Image.circle(20)
  count match {
    case 0 => unit
    case n => unit beside (unit above cross(n-1) above unit) beside unit
  }
}

Chessboard

We saw in the cross exercise that the hard part was identifying the recursive structure in what we were trying to create. Once we’d done that filling in the structural recursion pattern was straightforward.

In this exercise and the next we’re trying to sharpen you eye for recursive structure. Your mission in this exercise to identify the recursive structure in a chessboard, and implement a method to draw chessboards. The method skeleton isn’t

def chessboard(count: Int): Image =
  ???

In fig. 14 we have example chessboards drawn with count ranging from 0 to 2. Hint: note that now count does not give us the width of the chessboard, but tells us the number of atomic “chessboard units” we combine.

Figure 14: Chessboards generated by count from 0 to 2.

Implement chessboard.

def chessboard(count: Int): Image =
  count match {
    case 0 => <resultBase>
    case n => <resultUnit> <add> cross(n-1)
  }

val blackSquare = Image.rectangle(30, 30) fillColor Color.black
val redSquare   = Image.rectangle(30, 30) fillColor Color.red

val base =
  (redSquare   beside blackSquare) above (blackSquare beside redSquare)

def chessboard(count: Int): Image = {
  val blackSquare = Image.rectangle(30, 30) fillColor Color.black
  val redSquare   = Image.rectangle(30, 30) fillColor Color.red
  
  val base =
    (redSquare   beside blackSquare) above (blackSquare beside redSquare)
  count match {
    case 0 => base
    case n =>
      val unit = cross(n-1)
      (unit beside unit) above (unit beside unit)
  }
}

Sierpinkski Triangle

The Sierpinski triangle, show in fig. 15, is a famous fractal. (Technically, fig. 15 shows a Sierpinkski triangle.)

Figure 15: The Sierpinski triangle.

Although it looks complicated we can break the structure down into a form that we can generate with structural recursion over the natural numbers. Implement a method with skeleton

def sierpinski(count: Int): Image =
  ???

No hints this time. We’ve already seen everything we need to know.

def sierpinski(count: Int): Image = {
  val triangle = Image.triangle(10, 10) lineColor Color.magenta
  count match {
    case 0 => triangle above (triangle beside triangle)
    case n =>
      val unit = sierpinski(n-1)
      unit above (unit beside unit)
  }
}

7.5 Reasoning about Recursion

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

We’re now experienced users of structural recursion over the natural numbers. Let’s now return to our substitution model and see if it works with our new tool of recursion.

Recall that substution say we can substitute the value of an expression wherever we see a value. In the case of a method call, we can substitute the body of the method with appropriate renaming of the parameters.

Our very first example of recursion was boxes, written like so:

val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }

Let’s try using substitution on boxes(3) to see what we get.

Our first substitution is

boxes(3)
// Substitute body of `boxes`
3 match {
  case 0 => Image.empty
  case n => aBox beside boxes(n-1)
}

Knowing how to evaluate a match expression and using substitution again gives us

3 match {
  case 0 => Image.empty
  case n => aBox beside boxes(n-1)
}
// Substitute right-hand side expression of `case n`
aBox beside boxes(2)

We can substitute again on boxes(2) to obtain

aBox beside boxes(2)
// Substitute body of boxes
aBox beside {
  2 match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }
}
// Substitute right-hand side expression of `case n`
aBox beside {
  aBox beside boxes(1)
}

Repeating the process a few more times we get

aBox beside {
  aBox beside {
    1 match {
      case 0 => Image.empty
      case n => aBox beside boxes(n-1)
    }
  }
}
// Substitute right-hand side expression of `case n`
aBox beside {
  aBox beside {
      aBox beside boxes(0)
  }
}
// Substitute body of boxes
aBox beside {
  aBox beside {
    aBox beside {
      0 match {
        case 0 => Image.empty
        case n => aBox beside boxes(n-1)
      }
    }
  }
}
// Substitute right-hand side expression of `case 0`
aBox beside {
  aBox beside {
    aBox beside {
      Image.empty
    }
  }
}

Our final result, which simplies to

aBox beside aBox beside aBox beside Image.empty

is exactly what we expect. Therefore we can say that substitution works to reason about recursion. This is great! However the substitutions are quite complex and difficult to keep track of without writing them down. A more practical way to reason about recursion is to assume that the recursion works and only worry about what new comes from each step.

For example, when reasoning about boxes

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }

we can tell the base case is correct by inspection. Looking at the recursive case we assume that boxes(n-1) will do the right thing. We then ask ourselves “is what we do in the recursion case correct is the recursion itself is correct?” The answer is yes: if the recursion boxes(n-1) creates n-1 boxes in a line, sticking a box in front of them is the right thing to do. This way of reasoning is much more compact that using substitution and guaranteed to work if we’re using structural recursion.

Exercises

Below are some rather silly examples of structural recursion. Work out if the methods do what they claim to do without running them.

// Given a natural number, returns that number
// Examples: 
//   identity(0) == 0
//   identity(3) == 3
def identity(n: Int): Int =
  n match {
    case 0 => 0
    case n => 1 + identity(n-1)
  }

// Given a natural number, double that number
// Examples: 
//   double(0) == 0
//   double(3) == 6
def double(n: Int): Int =
  n match {
    case 0 => 0
    case n => 2 * double(n-1)
  }

def double(n: Int): Int =
  n match {
    case 0 => 0
    case 1 => 1
    case n => 2 * double(n-1)
  }

2(n-1 + 1) == 2(n-1) + 2

def double(n: Int): Int =
  n match {
    case 0 => 0
    case n => 2 + double(n-1)
  }

7.6 Auxillary Parameters

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._
val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)

We’ve seen how to use structural recursion over the natural numbers to write a number of interesting programs. In this section we’re going to see an extension that allows us to write more complex programs using auxillary parameters. An auxillary parameter is just an additional parameter to our method that allows us to pass extra information down the recursive call.

For example, imagine creating the picture in fig. 16, which shows a line of boxes that grow in size as we move along the line.

Figure 16: Boxes that grow in size with each recursion.

How can we create this image?

We know it has to be a structural recursion over the natural numbers, so we can immediately write down the skeleton

def growingBoxes(count: Int): Image =
  count match {
    case 0 => base
    case n => unit add growingBoxes(n-1)
  }

Using what we learned working with boxes earlier we can go a bit further and write down

def growingBoxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => Image.rectangle(???,???) beside growingBoxes(n-1)
  }

The challenge becomes how to make the box grow in size as we move to the right.

There are two ways to do this. The tricky way is to switch the order in the recursive case and make the size of the box a function of n. Here’s the code.

def growingBoxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => growingBoxes(n-1) beside Image.rectangle(n*10, n*10)
  }

Spend some time figuring out why this works before moving on to the solution using an auxillary parameter.

Using an auxillary parameter we simply add another parameter to growingBoxes that tells us how big the current box should be. When we recurse we change this size. Here’s the code.

def growingBoxes(count: Int, size: Int): Image =
  count match {
    case 0 => Image.empty
    case n => Image.rectangle(size, size) beside growingBoxes(n-1, size + 10)
  }

The auxillary parameter method has two advantages: we only have to think about what changes from one recursion to the next (in this case, the box gets larger), and it allows the caller to change this parameter (for example, making the starting box larger or smaller).

Now we’ve seen the auxillary parameter method let’s practice using it.

Gradient Boxes

In this exercise we’re going to draw a picture like that in fig. 17. We already know how to draw a line of boxes. The challenge in this exercise is to make the color change at each step.

Hint: you can spin the fill color at each recursion.

Figure 17: Five boxes filled with changing colors starting from Royal Blue

def gradientBoxes(n: Int, color: Color): Image =
  n match {
    case 0 => Image.empty
    case n => aBox.fillColor(color) beside gradientBoxes(n-1, color.spin(15.degrees))
  }

def gradientBoxes(n: Int): Image =
  n match {
    case 0 => Image.empty
    case n => aBox.fillColor(Color.royalBlue.spin((15*n).degrees)) beside gradientBoxes(n-1)
  }

Concentric Circles

Now let’s try a variation on the theme, drawing concentric circles as shown in fig. 18. Here we are changing the size rather than the color of the image at each step. Otherwise the pattern stays the same. Have a go at implementing it.

Figure 18: Concentric circles, colored Royal Blue

def concentricCircles(count: Int, size: Int): Image =
  count match {
    case 0 => Image.empty
    case n => Image.circle(size) on concentricCircles(n-1, size + 5)
  }

Once More, With Feeling

Now let’s combine both techniques to change size and color on each step, giving results like those shown in fig. 19. Experiment until you find something you like.

Figure 19: Concentric circles with interesting color variations

def circle(size: Int, color: Color): Image =
  Image.circle(size).lineWidth(3.0).lineColor(color)

def fadeCircles(n: Int, size: Int, color: Color): Image =
  n match {
    case 0 => Image.empty
    case n => circle(size, color) on fadeCircles(n-1, size+7, color.fadeOutBy(0.05.normalized))
  }

def gradientCircles(n: Int, size: Int, color: Color): Image =
  n match {
    case 0 => Image.empty
    case n => circle(size, color) on gradientCircles(n-1, size+7, color.spin(15.degrees))
  }

def image: Image =
  fadeCircles(20, 50, Color.red) beside gradientCircles(20, 50, Color.royalBlue)

7.7 Nested Methods

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

A method is a declaration. The body of a method can contain declarations and expressions. Therefore, a method declaration can contiain other method declarations.

To see why this is useful, lets look at a method we wrote earlier:

def cross(count: Int): Image = {
  val unit = Image.circle(20)
  count match {
    case 0 => unit
    case n => unit beside (unit above cross(n-1) above unit) beside unit
  }
}

We have declared unit inside the method cross. This means the declaration of unit is only in scope within the body of cross. It is good practice to limit the scope of declarations to the minimum needed, to avoid accidentally shadowing othering declarations. However, let’s consider the runtime behavior of cross and we’ll see that is has some undesireable characteristics.

We’ll use our substitution model to expand cross(1).

cross(1)
// Expands to
{
  val unit = Image.circle(20)
  1 match {
    case 0 => unit
    case n => unit beside (unit above cross(n-1) above unit) beside unit
  }
}
// Expands to
{
  val unit = Image.circle(20)
  unit beside (unit above cross(0) above unit) beside unit
}
// Expands to
{
  val unit = Image.circle(20)
  unit beside (unit above 
  {
    val unit = Image.circle(20)
    0 match {
      case 0 => unit
      case n => unit beside (unit above cross(n-1) above unit) beside unit
    }
  }
  above unit) beside unit
}
// Expands to
{
  val unit = Image.circle(20)
  unit beside (unit above 
  {
    val unit = Image.circle(20)
    unit
  }
  above unit) beside unit
}

The point of this enormous expansion is to demonstrate that we’re recreating unit every time we recurse within cross. We can prove this is true by printing something every time unit is created.

def cross(count: Int): Image = {
  val unit = { 
    println("Creating unit")
    Image.circle(20)
  }
  count match {
    case 0 => unit
    case n => unit beside (unit above cross(n-1) above unit) beside unit
  }
}

cross(1)

This doesn’t matter greatly for unit because it’s very small, but we could be doing that takes up a lot of memory or time, and it’s undesireable to repeat it when we don’t have to.

We could solve this by shifting unit outside of cross.

val unit = { 
  println("Creating unit")
  Image.circle(20)
}

def cross(count: Int): Image = {
  count match {
    case 0 => unit
    case n => unit beside (unit above cross(n-1) above unit) beside unit
  }
}

cross(1)

This is undesirable because unit now has a larger scope than needed. A better solution it to use a nested or internal method.

def cross(count: Int): Image = {
  val unit = { 
    println("Creating unit")
    Image.circle(20)
  }
  def loop(count: Int): Image = {
    count match {
      case 0 => unit
      case n => unit beside (unit above loop(n-1) above unit) beside unit
    }
  }

  loop(count)
}

cross(1)

This has the behavior we’re after, creating unit only once while minimising its scope. The internal method loop is using structural recursion exactly as before. We just need to ensure that we call it in cross. I usually name this sort of internal method loop or iter (short for iterate) to indicate that they’re performing a loop.

This technique is just a small variation of what we’ve done already, but let’s do a few exercises to make sure we’ve got the pattern.

Exercises

Chessboard

Rewrite chessboard using a nested method so that blackSquare, redSquare, and base are only created once when chessboard is called.

def chessboard(count: Int): Image = {
  val blackSquare = Image.rectangle(30, 30) fillColor Color.black
  val redSquare   = Image.rectangle(30, 30) fillColor Color.red
  
  val base =
    (redSquare   beside blackSquare) above (blackSquare beside redSquare)
  count match {
    case 0 => base
    case n =>
      val unit = cross(n-1)
      (unit beside unit) above (unit beside unit)
  }
}

def chessboard(count: Int): Image = {
  val blackSquare = Image.rectangle(30, 30) fillColor Color.black
  val redSquare   = Image.rectangle(30, 30) fillColor Color.red
  val base =
    (redSquare   beside blackSquare) above (blackSquare beside redSquare)
  def loop(count: Int): Image =
    count match {
      case 0 => base
      case n =>
        val unit = loop(n-1)
        (unit beside unit) above (unit beside unit)
    }
    
  loop(count)
}

Boxing Clever

Rewrite boxes, shown below, so that aBox is only in scope within boxes and only created once when boxes is called.

val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }

def boxes(count: Int): Image = {
  val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
  count match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }
}

def boxes(count: Int): Image = {
  val aBox = Image.rectangle(20, 20).fillColor(Color.royalBlue)
  def loop(count: Int): Image =
    count match {
      case 0 => Image.empty
      case n => aBox beside loop(n-1)
    }
    
  loop(count)
}

7.8 Conclusions

In this chapter we’ve seen our first big pattern for structuring code, structural recursion over the natural numbers. We’ve seen a lot of examples that generate images, but we can use this pattern for anything that is transforming a natural number into anything else (including other natural numbers).

We’ll use this pattern, and other variants of structural recursion, throughout the book.

8 Horticulture and Higher-order Functions

In this chapter we’re going to learn how to draw flowers and to use functions as first-class values. A first-class value is something we can pass as a parameter to a method or return as a result from a method call. If we pass a function as an argument to another function then:

• the function that is passed is being used as a first-class value; and
• the function that is receiving the function parameter is a called a higher-order function.

This terminology is not especially important, but you’ll encounter it in other writing so it’s important to know (at least vaguely) what it means. It will soon become clearer when we see some examples.

So far we have used the terms function and method interchangably. We’ll soon see that in Scala these two terms have distinct, though related, meanings.

Enough background. Let’s dive in to see:

• how we create functions in Scala; and
• how we use first-class functions to structure programs.

Our motivating example for this will be drawing flowers as in fig. 20.

Figure 20: A flower created using the techniques in this chapter

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

8.1 Parametric Curves

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

We’ll start by drawing a circle. We already know how to do this. Just write circle(10).draw, for example. Instead of using the built-in method, however, let’s plot points on a circle ourselves. This will give us the control we need to change the change the shape of the circle, producing a flower shape.

We can define a circle using what’s called a parametric equation. This is a fancy term for a function that takes some input (the parameter in parametric) and returns an x and y coordinate.

In Doodle we have a Point type to represent a position in two dimensions. We have two equivalent representations in terms of:

• x and y coordinates, called a cartesian representation; and
• in terms of an angle and distance at that angle from the origin (the radius), called a polar representation.

We can create points in the carteisan representation using Point.cartesian, and in the polar representation using Point.polar. The table below shows the main methods on Point.

For our input we’ll take an Angle, which tells us where on the circle we are. So for us, our parametric equations will be methods or functions from Angle to Point. A bit of geometry shows us that given an angle angle and x and y coordinates should be cos(angle) and sin(angle) respectively. We can define the parametric equation for a circle like so:

def parametricCircle(angle: Angle): Point =
  Point.cartesian(angle.cos, angle.sin)

Now we could sample a point on the circle every, say, 1 degree, giving us some fairly closely spaced points around the perimeter of the circle. To create an image we can draw something at each point (say, a triangle). We haven’t yet seen how to do this in Doodle. We can use the at method to put an Image as a specific point relative. This method takes a vector, with type Vec. We can convert a Point to a Vec using the toVec method³. Here’s the code.

def sample(start: Angle, increment: Angle): Image = {
  if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
    Image.empty
  else
    triangle(10, 10) at (parametricCircle(start).toVec) on sample(start+increment, increment)
}

This is a structural recursion, which is hopefully a familiar pattern by now.

If we draw this we’ll see a whole lot of triangles on top of each other—the circle we define with parametricCircle only has a radius of one! We need to make the circle a bit bigger. Let’s make the circle have a radius of 100 units.

def sample(start: Angle, increment: Angle): Image = {
  if(start > Angle.one) { // Angle.one is one complete turn. I.e. 360 degrees 
    Image.empty
  } else {
    val pt = parametricCircle(start)
    triangle(10, 10) at (Point.polar(pt.r * 100, pt.angle).toVec) on sample(start+increment, increment)
  }
}

See fig. 21, which shows the result of sample(0.degrees, 5.degrees).

Figure 21: Triangles arranged in a circle, using the code from sample above.

8.1.1 Flowers

The next step to creating a flower is to using a more interesting shape than a circle. That means changing parametricCircle for a more interesting equation. Perhaps rose below.

// Parametric equation for rose with k = 7
def rose(angle: Angle) =
  Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)

We can change sample to call rose instead of parametricCircle, but this is a bit unsatisfactory. What if we want to experiment with different parametric equations? It would be nice if we could pass to sample the method that creates points (i.e. the parametric equation). Can we do this? To do so we need to answer at least:

• how do we write down the type of a method as a method parameter?
• how do we differentiate between calling a method (e.g. rose(0.degress)) and referring to the method itself.

Let’s look at the second problem. If we try referring to a method without calling it we get an error.

rose

The error message handily tells us what we need to do, and this is a good point to finally introduce functions.

8.2 Functions

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

As the error message above suggests, we can convert any method to a function using the _ operator and call it with the same parameters.

// Parametric equation for rose with k = 7
def rose(angle: Angle) =
  Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)
  
rose _

(rose _)(0.degrees)

A function is basically a method, but we can use a function as a first-class value:

• we can pass it as an argument to a method or function;
• we can return it from a method or function; and
• we can give it a name using val.

val roseFn = rose _
roseFn(0.degrees)

8.2.1 Function Types

To pass functions to methods we need to know how to write down their types (because when we declare a parameter we have to declare its type).

We write a function type like (A, B) => C where A and B are the types of the parameters and C is the result type. The same pattern generalises from functions of no arguments to an arbitrary number of arguments.

In our example above we want f to be a function that accepts two Ints as parameters and returns an Int. Thus we can write it as (Int, Int) => Int.

(A, B, ...) => C

A => B

8.2.2 Function Literals

There is a literal syntax for functions. For example, here is a function that adds 42 to its input.

(x: Int) => x + 42

We can apply the function to an argument in the usual way.

val add42 = (x: Int) => x + 42
add42(0)

(parameter: type, ...) => expression

8.2.3 Functions as Objects

Because Scala is an object oriented language, all first class values are objects. This means functions can have methods, including some useful means for composition:

val addTen = (a: Int) => a + 10
val double = (a: Int) => a * 2
val combined = addTen andThen double // this composes the two functions
combined(5)

Exercises

Function Types

What is the type of the function roseFn defined above? What does this type mean?

Function Literals

Write roseFn as a function literal.

val roseFn = (angle: Angle) =>
  Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)

8.3 Higher Order Methods and Functions

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

Why are functions useful? We can already use methods to package up and name reusable fragments of code. What other advantages do we get from treating code as values? We’ve said we can

• pass functions as parameters to other functions and methods; and
• create methods that return functions as their results

but we haven’t used this ability yet. Let’s do that now.

Let’s consider the pattern from the concentric circles exercise as an example:

def singleShape: Image = ???

def manyShapes(n: Int): Image =
  if(n == 1) {
    singleShape
  } else {
    singleShape on manyShapes(n - 1)
  }

This pattern allows us to create many different images by changing the definition of singleShape. However, each time we provide a new definition of singleShape, we also need a new definition of manyShapes to go with it.

We can make manyShapes completely general by supplying singleShape as a parameter:

def manyShapes(n: Int, singleShape: Int => Image): Image =
  if(n == 1) {
    singleShape(n)
  } else {
    singleShape(n) on manyShapes(n - 1, singleShape)
  }

Now we can re-use the same definition of manyShapes to produce plain circles, circles of different hue, circles with different opacity, and so on. All we have to do is pass in a suitable definition of singleShape:

// Passing a function literal directly:
val blackCircles: Image =
  manyShapes(10, (n: Int) => Circle(50 + 5*n))

// Converting a method to a function:
def redCircle(n: Int): Image =
  Circle(50 + 5*n) lineColor Color.red

val redCircles: Image =
  manyShapes(10, redCircle _)

Exercises

The Colour and the Shape

Starting with the code below, write color and shape functions to produce the image shown in fig. 22.

Figure 22: Colours and Shapes

def manyShapes(n: Int, singleShape: Int => Image): Image =
  if(n == 1) {
    singleShape(n)
  } else {
    singleShape(n) on manyShapes(n - 1, singleShape)
  }

The manyShapes method is equivalent to the concentricCircles method from previous exercises. The main difference is that we pass in the definition of singleShape as a parameter.

Let’s think about the problem a little. We need to do two things:

1. write an appropriate definition of singleShape for each of the three shapes in the target image; and

2. call manyShapes three times, passing in the appropriate definition of singleShape each time and putting the results beside one another.

Let’s look at the definition of the singleShape parameter in more detail. The type of the parameter is Int => Image, which means a function that accepts an Int parameter and returns an Image. We can declare a method of this type as follows:

def outlinedCircle(n: Int) =
  Circle(n * 10)

We can convert this method to a function, and pass it to manyShapes to create an image of concentric black outlined circles:

manyShapes(10, outlinedCircle _)

This produces the output shown in fig. 23.

Figure 23: Many outlined circles

The rest of the exercise is just a matter of copying, renaming, and customising this function to produce the desired combinations of colours and shapes:

def circleOrSquare(n: Int) =
  if(n % 2 == 0) Rectangle(n*20, n*20) else Circle(n*10)

(manyShapes(10, outlinedCircle) beside manyShapes(10, circleOrSquare))

See fig. 24 for the output.

Figure 24: Many outlined circles beside many circles and squares

For extra credit, when you’ve written your code to create the sample shapes above, refactor it so you have two sets of base functions—one to produce colours and one to produce shapes. Combine these functions using a combinator as follows, and use the result of the combinator as an argument to manyShapes

  def colored(shape: Int => Image, color: Int => Color): Int => Image =
    (n: Int) => ???

def manyShapes(n: Int, singleShape: Int => Image): Image =
  if(n == 1) {
    singleShape(n)
  } else {
    singleShape(n) on manyShapes(n - 1, singleShape)
  }

def rainbowCircle(n: Int) = {
  val color = Color.blue desaturate 0.5.normalized spin (n * 30).degrees
  val shape = Circle(50 + n*12)
  shape lineWidth 10 lineColor color
}

def fadingTriangle(n: Int) = {
  val color = Color.blue fadeOut (1 - n / 20.0).normalized
  val shape = Triangle(100 + n*24, 100 + n*24)
  shape lineWidth 10 lineColor color
}

def rainbowSquare(n: Int) = {
  val color = Color.blue desaturate 0.5.normalized spin (n * 30).degrees
  val shape = Rectangle(100 + n*24, 100 + n*24)
  shape lineWidth 10 lineColor color
}

val answer =
  (manyShapes(10, rainbowCircle) beside
   manyShapes(10, fadingTriangle) beside
   manyShapes(10, rainbowSquare))

def manyShapes(n: Int, singleShape: Int => Image): Image =
  if(n == 1) {
    singleShape(n)
  } else {
    singleShape(n) on manyShapes(n - 1, singleShape)
  }

def colored(shape: Int => Image, color: Int => Color): Int => Image =
  (n: Int) =>
    shape(n) lineWidth 10 lineColor color(n)

def fading(n: Int): Color =
  Color.blue fadeOut (1 - n / 20.0).normalized

def spinning(n: Int): Color =
  Color.blue desaturate 0.5.normalized spin (n * 30).degrees

def size(n: Int): Double =
  50 + 12 * n

def circle(n: Int): Image =
  Circle(size(n))

def square(n: Int): Image =
  Rectangle(2*size(n), 2*size(n))

def triangle(n: Int): Image =
  Triangle(2*size(n), 2*size(n))

val answer =
  (manyShapes(10, colored(circle, spinning)) beside
   manyShapes(10, colored(triangle, fading)) beside
   manyShapes(10, colored(square, spinning)))

8.4 Exercises

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

Now we are chock full of knowledge about functions, we’re going to return to the problem of drawing flowers. We’ll be asking you to do more design work here than we have done previously.

Your task is to break down the task of drawing a flower into small functions that work together. Try to give yourself as much creative freedom as possible, by breaking out each individual component of the task into a function.

Try to do this now. If you run into problems look at our decomposition below.

8.4.1 Components

We’ve identified two components of drawing flowers:

• the parametric equation; and
• the structural recursion over angles.

What other components might we abstract into functions? What are their types? (This is a deliberately open ended question. Explore!)

def scale(factor: Double): Point => Point = 
  (pt: Point) => {
    Point.polar(pt.r * factor, pt.angle)
  }

def parametricCircle(angle: Angle): Point =
  Point.cartesian(angle.cos, angle.sin)

def sample(start: Angle, increment: Angle, location: Angle => Point): Image = {
  if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
    Image.empty
  else
    triangle(10, 10) at location(start).toVec on sample(start+increment, increment, location)
}

def sample(start: Angle, increment: Angle): Image = {
  if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
    Image.empty
  else
    triangle(10, 10) at (parametricCircle(start).toVec) on sample(start+increment, increment)
}

def sample(start: Angle, increment: Angle, empty: Image, combine: (Angle, Image) => Image): Image = {
  if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
    empty
  else
    combine(start, sample(start+increment, increment, empty, combine))
}

8.4.2 Combine

Now we’ve broken out the components we can combine them to create interesting results. Do this now.

def parametricCircle(angle: Angle): Point =
  Point.cartesian(angle.cos, angle.sin)
  
def rose(angle: Angle): Point =
  Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)

def scale(factor: Double): Point => Point = 
  (pt: Point) => {
    Point.polar(pt.r * factor, pt.angle)
  }

def sample(start: Angle, increment: Angle, location: Angle => Point): Image = {
  if(start > Angle.one) // Angle.one is one complete turn. I.e. 360 degrees
    Image.empty
  else
    triangle(10, 10) at location(start).toVec on sample(start+increment, increment, location)
}

def locate(scale: Point => Point, point: Angle => Point): Angle => Point =
  (angle: Angle) => scale(point(angle))

// Rose on circle
val flower = {
  sample(0.degrees, 5.degrees, locate(scale(200), rose _)) on
  sample(0.degrees, 5.degrees, locate(scale(150), parametricCircle _)) 
}

8.4.3 Experiment

Now experiment with the creative possibilities open to you!

9 Shapes, Sequences, and Stars

In this chapter we will learn how to build our own shapes out of the primitve lines and curves that make up the triangles, rectangles, and circles we’ve used so far. In doing so we’ll learn how to represent sequences of data, and manipulate such sequences using higher-order functions that abstract over structural recursion. That’s quite a lot of jargon, but we hope you’ll see it’s not as difficult as it sounds!

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

9.1 Paths

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

All shapes in Doodle are ultimately represented as paths. You can think of a path as giving a sequence of movements for an imaginary pen, starting from the origin. Pen movements come in three varieties:

• moving the pen to a point without drawing a line;

• drawing a straight line from the current position to a point; and

• drawing a Bezier curve from the current position to a point, with the shape of the curve determined by two control points.

Paths themselves come in two varieties:

• open paths, where the end of the path is not necessarily the starting point; and
• closed paths, that end where they begin—and if the path doesn’t end where it started a line will be inserted to make it so.

The picture in fig. 25 illustrates the components that can make up a path, and shows the difference between open and closed paths.

Figure 25: The same paths draw as open (top) and closed (bottom) paths. Notice how the open triangle is not properly joined at the bottom left, and the closed curve inserts a straight line to close the shape.

9.1.1 Creating Paths

Now we know about paths, how do we create them in Doodle? Here’s the code that created fig. ??.

import doodle.core.Point._

val triangle =
  List(
    LineTo(cartesian(50, 100)),
    LineTo(cartesian(100, 0)),
    LineTo(cartesian(0, 0))
  )

val curve =
  List(BezierCurveTo(cartesian(50, 100), cartesian(100, 100), cartesian(150, 0)))

def style(image: Image): Image =
  image.
    lineWidth(6.0).
    lineColor(Color.royalBlue).
    fillColor(Color.skyBlue)

val openPaths =
  style(openPath(triangle) beside openPath(curve))

val closedPaths =
  style(closedPath(triangle) beside closedPath(curve))

val paths = openPaths above closedPaths

From this code we can see we create paths using the openPath and closePath methods on Image, just we create other shapes. A paths is created from a List of PathElement. The different kinds of PathElement are described in tbl. 4.

Constructing a List is straight-forward: we just call List with the elements we want the list to contain. Here are some examples.

// List of Int
List(1, 2, 3)

// List of Image
List(circle(10), circle(20), circle(30))

// List of Color
List(Color.paleGoldenrod, Color.paleGreen, Color.paleTurquoise)

Notice the type of a List includes the type of the elements, written in square brackets. So the type of a list of integers is written List[Int] and a list of PathElement is written List[PathElement].

Exercises

Polygons

Create paths to define a triangle, square, and pentagon. Your image might look like fig. 26. Hint: you might find it easier to use polar coordinates to define the polygons.

Figure 26: A triangle, square, and pentagon, defined using paths.

import doodle.core.Point._
import doodle.core.Color._

val triangle =
  closedPath(List(
               MoveTo(polar(50, 0.degrees)),
               LineTo(polar(50, 120.degrees)),
               LineTo(polar(50, 240.degrees))
             ))

val square =
  closedPath(List(
               MoveTo(polar(50, 45.degrees)),
               LineTo(polar(50, 135.degrees)),
               LineTo(polar(50, 225.degrees)),
               LineTo(polar(50, 315.degrees))
             ))

val pentagon =
  closedPath((List(
                MoveTo(polar(50, 72.degrees)),
                LineTo(polar(50, 144.degrees)),
                LineTo(polar(50, 216.degrees)),
                LineTo(polar(50, 288.degrees)),
                LineTo(polar(50, 360.degrees))
              )))

val spacer =
  rectangle(10, 100).noLine.noFill

def style(image: Image): Image =
  image.lineWidth(6.0).lineColor(paleTurquoise).fillColor(turquoise)

val image = 
  style(triangle) beside spacer beside style(square) beside spacer beside style(pentagon)

Curves

Repeat the exercise above, but this time use curves instead of straight lines to create some interesting shapes. Our curvy polygons are shown in fig. 27. Hint: you’ll have an easier time if you abstract into a method your code for creating a curve.

Figure 27: A curvy triangle, square, and polygon, defined using paths.

import doodle.core.Point._
import doodle.core.Color._

def curve(radius: Int, start: Angle, increment: Angle): PathElement = {
  BezierCurveTo(
    polar(radius *  .8, start + (increment * .3)),
    polar(radius * 1.2, start + (increment * .6)),
    polar(radius, start + increment)
  )
}

val triangle =
  closedPath(List(
               MoveTo(polar(50, 0.degrees)),
               curve(50, 0.degrees, 120.degrees),
               curve(50, 120.degrees, 120.degrees),
               curve(50, 240.degrees, 120.degrees)
             ))

val square =
  closedPath(List(
               MoveTo(polar(50, 45.degrees)),
               curve(50, 45.degrees, 90.degrees),
               curve(50, 135.degrees, 90.degrees),
               curve(50, 225.degrees, 90.degrees),
               curve(50, 315.degrees, 90.degrees)
             ))

val pentagon =
  closedPath((List(
                MoveTo(polar(50, 72.degrees)),
                curve(50, 72.degrees, 72.degrees),
                curve(50, 144.degrees, 72.degrees),
                curve(50, 216.degrees, 72.degrees),
                curve(50, 288.degrees, 72.degrees),
                curve(50, 360.degrees, 72.degrees)
              )))

val spacer =
  rectangle(10, 100).noLine.noFill

def style(image: Image): Image =
  image.lineWidth(6.0).lineColor(paleTurquoise).fillColor(turquoise)

val image = style(triangle) beside spacer beside style(square) beside spacer beside style(pentagon)

9.2 Working with Lists

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

At this point you might be thinking it would be nice to create a method to draw polygons rather than constructing each one by hand. There is clearly a repeating pattern to their construction and we should be able to abstact this pattern but we don’t know how to create a list of arbitrary size. It’s time we learned more about building and manipulating lists.

9.2.1 The Recursive Structure of Lists

You’ll recall when we introduced structural recursion over the natural numbers we said we could transform their recursive structure into any other recursive structure. We demonstrated this for concentric circles and a variety of other patterns.

Lists have a recursive structure, and one that is very similar to the structure of the natural numbers. A List is

• the empty list Nil; or
• a pair of an element a and a List, written a :: tail, where tail is the rest of the list.

For example, we can write out the list List(1, 2, 3, 4) in its “long” form as

1 :: 2 :: 3 :: 4 :: Nil

Notice the similarity to the natural numbers. Earlier we noted we can expand the structure of a natural number so we could write, say, 3 as 1 + 1 + 1 + 0. If we replace + with :: and 0 with Nil we get the List 1 :: 1 :: 1 :: Nil.

What does this mean? It means we can easily transform a natural number into a List using our famililar tool of structural recursion⁴. Here’s a very simple example, which given a number builds a list of that length containing the String “Hi”.

def sayHi(length: Int): List[String] =
  length match {
    case 0 => Nil
    case n => "Hi" :: sayHi(n - 1)
  }

sayHi(5)

This recursive structure also means we can transform lists into other recursive structures, such a natural numbers, different lists, chessboards, and so on. Here we increment every element a list—that is, transform a list to a list—using structural recursion.

def increment(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd + 1) :: tl
  }
  
increment(List(1, 2, 3))

Here we sum the elements of a list of integers—that is, transform a list to a natural number—using structural recursion.

def sum(list: List[Int]): Int =
  list match {
    case Nil => 0
    case hd :: tl => hd + sum(tl)
  }
  
sum(List(1, 2, 3)) 

9.2.2 Type Variables

What about finding the length of a list? We know we can use our standard tool of structural recursion to write the method. Here’s the code to calculate the length of a List[Int].

def length(list: List[Int]): Int =
  list match {
    case Nil => 0
    case hd :: tl => 1 + length(tl)
  }

Note that we don’t do anything with the elements of the list—we don’t really care about their type. Using the same code skeleton can just as easily calculate the length of a List[Int] as a List[HairyYak] but we don’t currently know how to write down the type of a list where we don’t care about the type of the elements.

Scala lets us write methods that can work with any type, by using what is called a type variable. A type variable is written in square brackets like [A] and comes after the method name and before the parameter list. A type variable can stand in for any specific type, and we can use it in the parameter list or result type to indicate some type that we don’t know up front. For example, here’s how we can write length so it works with lists of any type.

def length[A](list: List[A]): Int =
  list match {
    case Nil => 0
    case hd :: tl => 1 + length(tl)
  }

def doSomething[A,B](list: List[A]): B =
  list match {
    case Nil => ??? // Base case of type B here
    case hd :: tl => f(hd, doSomething(tl))
  }  

Exercises

Building Lists

In these exercises we get some experience constructing lists using structural recursion on the natural numbers.

Write a method called ones that accepts an Int n and returns a List[Int] with length n and every element 1. For example

def ones(n: Int): List[Int] =
  n match {
    case 0 => Nil
    case n => 1 :: ones(n - 1)
  }

ones(3)

def ones(n: Int): List[Int] =
  n match {
    case 0 => Nil
    case n => 1 :: ones(n - 1)
  }
  
ones(3)

Write a method descending that accepts an natural number n and returns a List[Int] containing the natural numbers from n to 1 or the empty list if n is zero. For example

def descending(n: Int): List[Int] =
  n match {
    case 0 => Nil
    case n => n :: descending(n - 1)
  }

descending(0)
descending(3)

def descending(n: Int): List[Int] =
  n match {
    case 0 => Nil
    case n => n :: descending(n - 1)
  }

descending(0)
descending(3)

Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero.

def ascending(n: Int): List[Int] = {
  def iter(n: Int, counter: Int): List[Int] =
    n match {
      case 0 => Nil
      case n => counter :: iter(n - 1, counter + 1) 
    }

  iter(n, 1)
}

ascending(0)
ascending(3)

def ascending(n: Int): List[Int] = {
  def iter(n: Int, counter: Int): List[Int] =
    n match {
      case 0 => Nil
      case n => counter :: iter(n - 1, counter + 1) 
    }

  iter(n, 1)
}
  
ascending(0)
ascending(3)

Create a method fill that accepts a natural number n and an element a of type A and constructs a list of length n where all elements are a.

def fill[A](n: Int, a: A): List[A] =
  n match {
    case 0 => Nil
    case n => a :: fill(n-1, a)
  }

fill(3, "Hi")
fill(3, Color.blue)

def fill[A](n: Int, a: A): List[A] =
  n match {
    case 0 => Nil
    case n => a :: fill(n-1, a)
  }

fill(3, "Hi")
fill(3, Color.blue)

Transforming Lists

In these exercises we practice the other side of list manipulation—transforming lists into elements of other types (and sometimes, into different lists).

Write a method double that accepts a List[Int] and returns a list with each element doubled.

def double(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd * 2) :: double(tl)
  }

double(List(1, 2, 3))
double(List(4, 9, 16))

def double(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd * 2) :: double(tl)
  }

double(List(1, 2, 3))
double(List(4, 9, 16))

Write a method product that accepts a List[Int] and calculates the product of all the elements.

def product(list: List[Int]): Int =
  list match {
    case Nil => 1
    case hd :: tl => hd * product(tl)
  }

product(Nil)
product(List(1,2,3))

def product(list: List[Int]): Int =
  list match {
    case Nil => 1
    case hd :: tl => hd * product(tl)
  }

product(Nil)
product(List(1,2,3))

Write a method contains that accepts a List[A] and an element of type A and returns true if the list contains the element and false otherwise.

def contains[A](list: List[A], elt: A): Boolean =
  list match {
    case Nil => false
    case hd :: tl => (hd == elt) || contains(tl, elt)
  }

contains(List(1,2,3), 3)
contains(List("one", "two", "three"), "four")

def contains[A](list: List[A], elt: A): Boolean =
  list match {
    case Nil => false
    case hd :: tl => (hd == elt) || contains(tl, elt)
  }

contains(List(1,2,3), 3)
contains(List("one", "two", "three"), "four")

Write a method first that accepts a List[A] and an element of type A and returns the first element of the list if it is not empty and otherwise returns the element of type A passed as a aprameter.

def first[A](list: List[A], elt: A): A =
  list match {
    case Nil => elt
    case hd :: tl => hd
  }

first(Nil, 4)
first(List(1,2,3), 4)

def first[A](list: List[A], elt: A): A =
  list match {
    case Nil => elt
    case hd :: tl => hd
  }
  
first(Nil, 4)
first(List(1,2,3), 4)

Challenge Exercise: Reverse

Write a method reverse that accepts a List[A] and reverses the list.

def reverse[A](list: List[A]): List[A] = {
  def iter(list: List[A], reversed: List[A]): List[A] =
    list match {
      case Nil => reversed
      case hd :: tl => iter(tl, hd :: reversed)
    }
    
  iter(list, Nil)
}

reverse(List(1, 2, 3))
reverse(List("a", "b", "c"))

def reverse[A](list: List[A]): List[A] = {
  def iter(list: List[A], reversed: List[A]): List[A] =
    list match {
      case Nil => reversed
      case hd :: tl => iter(tl, hd :: reversed)
    }
    
  iter(list, Nil)
}

reverse(List(1, 2, 3))
reverse(List("a", "b", "c"))

Polygons!

At last, let’s return to our example of drawing polygons. Write a method polygon that accepts the number of sides of the polygon and the starting rotation and produces a Image representing the specified regular polygon. Hint: use an internal accumulator.

Use this utility to create an interesting picture combining polygons. Our rather unimaginative example is in fig. 28. We’re sure you can do better.

Figure 28: Concentric polygons with pastel gradient fill.

import Point._

def polygon(sides: Int, size: Int, initialRotation: Angle): Image = {
  def iter(n: Int, rotation: Angle): List[PathElement] =
    n match {
      case 0 =>
        Nil
      case n =>
        LineTo(polar(size, rotation * n + initialRotation)) :: iter(n - 1, rotation)
    }
  closedPath(MoveTo(polar(size, initialRotation)) :: iter(sides, 360.degrees / sides))
}

def style(img: Image): Image = {
  img.
    lineWidth(3.0).
    lineColor(Color.mediumVioletRed).
    fillColor(Color.paleVioletRed.fadeOut(0.5.normalized))
}

def makeShape(n: Int, increment: Int): Image =
    polygon(n+2, n * increment, 0.degrees)

def makeColor(n: Int, spin: Angle, start: Color): Color =
  start spin (spin * n)

val baseColor = Color.hsl(0.degrees, 0.7.normalized, 0.7.normalized)

def makeImage(n: Int): Image = {
  n match {
    case 0 =>
      Image.empty
    case n =>
      val shape = makeShape(n, 10)
      val color = makeColor(n, 30.degrees, baseColor)
      makeImage(n-1) on (shape fillColor color)
  }
}

val image = makeImage(15)

9.3 Transforming Sequences

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

We’ve seen that using structural recursion we can create and transform lists. This pattern is simple to use and to understand, but it requires we write the same skeleton time and again. In this section we’ll learn that we can replace structural recursion in some cases by using a method on List called map. We’ll also see that other useful datatypes provide this method and we can use it as a common interface for manipulating sequences.

9.3.1 Transforming the Elements of a List

In the previous section we say several examples where we transformed one list to another. For example, we incremented the elements of a list with the following code.

def increment(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd + 1) :: tl
  }
  
increment(List(1, 2, 3))

In this example the structure of the list doesn’t change. If we start with three elements we end with three elements. We can abstract this pattern in a method called map. If we have a list with elements of type A, we pass map a function of type A => B and we get back a list with elements of type B. For example, we can implement increment using map with the function x => x + 1.

def increment(list: List[Int]): List[Int] =
  list.map(x => x + 1)
  
increment(List(1, 2, 3))

Each element is transformed by the function we pass to map, in this case x => x + 1. With map we can transform the elements, but we cannot change the number of elements in the list.

We find a graphical notation helps with understanding map. If we had some type Circle we can draw a List[Circle] as a box containing a circle, as shown in fig. 29.

Figure 29: A List[Circle] representing by a circle within a box

Now we can draw an equation for map as in fig. 30. If you prefer symbols instead of pictures, the picture is showing that List[Circle] map (Circle => Triangle) = List[Triangle]. One feature of the graphical representation is it nicely illustrates that map cannot create a new “box”, which represents the structure of the list—or more concretely the number of elements and their order.

Figure 30: map shown graphically

The graphical drawing of map exactly illustrates what holds at the type level for map. If we prefer we can write it down symbolically:

List[A] map (A => B) = List[B]

The left hand side of the equation has the type of the list we map and the function we use to do the mapping. The right hand is the type of the result. We can perform algebra with this reprsentation, substituting in concrete types from our program.

9.3.2 Transforming Sequences of Numbers

We have also written a lot of methods that transform a natural number to a list. We briefly discussed how we can represent a natural number as a list. 3 is equivalent to 1 + 1 + 1 + 0, which in turn we could represent as List(1, 1, 1). So what? Well, it means we could write a lot of the methods that accepts natural numbers as methods that worked on lists.

For example, instead of

def fill[A](n: Int, a: A): List[A] =
  n match {
    case 0 => Nil
    case n => a :: fill(n-1, a)
  }
  
fill(3, "Hi")

we could write

def fill[A](n: List[Int], a: A): List[A] =
  n.map(x => a)
  
fill(List(1, 1, 1), "Hi")

The implementation of this version of fill is more convenient to write, but it is much less convenient for the user to call it with List(1, 1, ,1) than just writing 3.

If we want to work with sequences of numbers we are better off using Ranges. We can create these using the until method of Int or Double:

0 until 10
0.0 until 5.0

Ranges have a by method that allows us to change the step between consecutive elements of the range:

0 until 10 by 2
0.0 until 1.0 by 0.3

Ranges also have a map method just like List

(0 until 3) map (x => x + 1) 

You’ll notice the result has type IndexedSeq and is implemented as a Vector—two types we haven’t seen yet. We can treat an IndexedSeq much like a List, but for simplicity we can convert a Range or an IndexedSeq to a List using the toList method.

(0 until 7).toList
(0 until 3).map(x => x + 1).toList

With Ranges in our toolbox we can write fill as

def fill[A](n: Int, a: A): List[A] =
  (0 until n).toList.map(x => a)
  
fill(3, "Hi")

Exercises

Ranges, Lists, and map

Using our new tools, reimplement the following methods.

Write a method called ones that accepts an Int n and returns a List[Int] with length n and every element is 1. For example

def ones(n: Int): List[Int] =
  (0 until n).toList.map(x => 1)

ones(3)

def ones(n: Int): List[Int] =
  (0 until n).toList.map(x => 1)
  
ones(3)

Write a method descending that accepts an natural number n and returns a List[Int] containing the natural numbers from n to 1 or the empty list if n is zero. For example

def descending(n: Int): List[Int] =
  (n until 0 by -1).toList

descending(0)
descending(3)

def descending(n: Int): List[Int] =
  (n until 0 by -1).toList

descending(0)
descending(3)

Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero.

def ascending(n: Int): List[Int] =
  (0 until n).toList.map(x => x + 1)

ascending(0)
ascending(3)

def ascending(n: Int): List[Int] = 
  (0 until n).toList.map(x => x + 1)
  
ascending(0)
ascending(3)

Write a method double that accepts a List[Int] and returns a list with each element doubled.

def double(list: List[Int]): List[Int] =
  list map (x => x * 2)

double(List(1, 2, 3))
double(List(4, 9, 16))

def double(list: List[Int]): List[Int] =
  list map (x => x * 2)

double(List(1, 2, 3))
double(List(4, 9, 16))

Polygons, Again!

Using our new tools, rewrite the polygon method from the previous section.

def polygon(sides: Int, size: Int, initialRotation: Angle): Image = {
  import Point._

  val step = (Angle.one / sides).toDegrees
  val path = 
    (0.0 to 360.0 by step).toList.map{ deg => 
      LineTo(polar(size, initialRotation + deg.degrees))
    }
    
  closedPath(MoveTo(polar(size, initialRotation)) :: path)
}

Challenge Exercise: Beyond Map

Can we use map to replace all uses of structural recursion? If not, can you characterise the problems that we can’t implement with map but can implement with general structural recursion over lists?

List[A] map A => B = List[B]

9.3.3 Tools with Ranges

We’ve seen the until method to construct Ranges, and the by method to change the increment in a Range. There is one more method that will be useful to know about: to. This constructs a Range like until but the Range includes the endpoint. Compare

1 until 5
1 to 5

In technical terms, the Range constructed with until is a half-open interval, while the range constructed with to is an open interval.

Exercises

Using Open Intervals

Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero. Hint: use to

def ascending(n: Int): List[Int] =
  (1 to n).toList

ascending(0)
ascending(3)

def ascending(n: Int): List[Int] = 
  (1 to n).toList
  
ascending(0)
ascending(3)

9.4 My God, It’s Full of Stars!

import doodle.core._
import doodle.core.Image._
import doodle.syntax._
import doodle.jvm.Java2DCanvas._
import doodle.backend.StandardInterpreter._

Let’s use our new tools to draw some stars. For the purpose of this exercise let’s assume that a star is a polygon with p points. However, instead of connecting each point to its neighbours, we’ll connect them to the nth point around the circumference.

For example, fig. 31 shows stars with p=11 and n=1 to 5. n=1 produces a regular polygon while values of n from 2 upwards produce stars with increasingly sharp points:

Figure 31: Stars with p=11 and n=1 to 5

Write code to draw the diagram above. Start by writing a method to draw a star given p and n:

def star(p: Int, n: Int, radius: Double): Image =
  ???

Hint: use the same technique we used for polygon previously.

def star(sides: Int, skip: Int, radius: Double): Image = {
  import Point._

  val rotation = 360.degrees * skip / sides

  val start = MoveTo(polar(radius, 0.degrees))
  val elements = (1 until sides).toList map { index =>
    val point = polar(radius, rotation * index)
    LineTo(point)
  }

  closedPath(start :: elements) lineWidth 2
}

Using structural recursion and beside write a method allBeside with the signature

def allBeside(images: List[Image]): Image =
  ???

We’ll use allBeside to create the row of stars. To create the picture we only need to use values of skip from 1 to sides/2 rounded down. For example:

def allBeside(imgs: List[Image]): Image =
  imgs match {
    case Nil => Image.empty
    case hd :: tl => hd beside allBeside(tl)
  }

allBeside(
  (1 to 5).toList map { skip =>
    star(11, skip, 100)
  }
)